package lc.q51_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
 *
 * 你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
 *
 * 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
 *
 * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
 *
 */
public class Q68 {
    public List<String> fullJustify(String[] words, int maxWidth) {
        // 基本思路就是拿一行去插
        List<String> strings = new ArrayList<>();
        List<String> s = new ArrayList<>();
        int remain = maxWidth;
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (s.size() > 0) {
                remain --;
            }
            if (word.length() > remain) {
                int size = s.size();
                // 根据size设计空格数
                StringBuilder sb = new StringBuilder();
                if (size == 1) {
                    sb.append(s.get(0));
                    while (sb.length() < maxWidth) {
                        sb.append(' ');
                    }
                } else {
                    int totalSpace = remain + size;
                    // 放置多少空格怎么决定
                    // 尽量平均，前>=后
                    int[] perSizes = new int[size - 1];
                    int rem = totalSpace;
                    int _t = size - 1;
                    while (rem > 0 && _t > 0) {
                        int ps = rem / _t;
                        for (int j = 0; j < _t; j++) {
                            perSizes[j] += ps;
                            rem -= ps;
                        }
                        _t --;
                    }
                    for (int j = 0; j < s.size(); j++) {
                        if (j != 0) {
                            char[] chars = new char[perSizes[j-1]];
                            Arrays.fill(chars, ' ');
                            sb.append(chars);
                        }
                        sb.append(s.get(j));
                    }
                }

                strings.add(sb.toString());
                s.clear();
                remain = maxWidth;
            }
            s.add(word);
            remain -= word.length();
        }
        StringBuilder sb = new StringBuilder();
        for (String s1 : s) {
            sb.append(s1);
            if (sb.length() < maxWidth) {
                sb.append(' ');
            }
        }
        while (sb.length() < maxWidth) {
            sb.append(' ');
        }
        strings.add(sb.toString());
        return strings;
    }

    public static void main(String[] args) {
        Q68 q68 = new Q68();
        String[] words = new String[]{"ask","not","what","your","country","can","do","for","you","ask","what","you","can","do","for","your","country"};
        List<String> x = q68.fullJustify(words, 16);
        for (String s : x) {
            System.out.println("\"" +s +"\"");
        }
    }
}
